package dg;

import java.util.*;

public class Apriori {
    // 支持度阈值Apriori
    private final static int SUPPORT = 3;
    // 置信度阈值
    private final static double CONFIDENCE = 0.8;

    public static void main(String[] args) {
        ArrayList<String> itemCheckList = new ArrayList<>();
        itemCheckList.add("f;a;c;d;g;i;m;p");
        itemCheckList.add("a;b;c;f;l;m;o");
        itemCheckList.add("b;f;h;j;o");
        itemCheckList.add("b;c;k;s;p");
        itemCheckList.add("a;f;c;e;l;p;m;n");

        Apriori apriori = new Apriori();
        apriori.apriori(itemCheckList);
    }

    /**
     * apriori 的主运算程序
     *
     * @param dataList
     * @return
     */
    private void apriori(ArrayList<String> dataList) {
        Set<String> itemSet = new HashSet<>();
        Map<String, Integer> itemIdMap = new HashMap<>();
        Map<Integer, String> idItemMap = new HashMap<>();
        List<Integer> itemChecklist = new ArrayList<>();
        List<List<Integer>> countList = new ArrayList<>();
        Map<Integer, Integer> frequentMap = new HashMap<>();
        getItemSetAndCreateItemIndex(dataList, itemSet, itemChecklist, itemIdMap, idItemMap);
        List<Integer> selectedItemList = createFirstFrequentSet(itemSet, itemChecklist, itemIdMap, frequentMap);
        countList.add(selectedItemList);
        List<Integer> currentFrequentCountList = countList.get(0);
        int pointCount = 2;
        while (!currentFrequentCountList.isEmpty()) {
            currentFrequentCountList = setFrequentSetMap(currentFrequentCountList, frequentMap, pointCount, itemChecklist);
            pointCount++;
            if (!currentFrequentCountList.isEmpty()) {
                countList.add(currentFrequentCountList);
            }
        }

        for (int i = 0; i < countList.size() - 1; i++) {
            for (int j = i + 1; j < countList.size(); j++) {
                createAssociationRule(countList.get(i), countList.get(j), frequentMap, idItemMap);
            }
        }

//        Set<Map.Entry<Integer, Integer>> entries = frequentMap.entrySet();
//        for (Map.Entry<Integer, Integer> entry : entries) {
//            System.out.println(getItemStr(entry.getKey(), idItemMap) + " = " + entry.getValue());
//        }

    }

    private List<Integer> setFrequentSetMap(List<Integer> currentFrequentCountList, Map<Integer, Integer> frequentMap, int pointCount, List<Integer> itemChecklist) {
        List<Integer> newCurrentFrequentCountList = new ArrayList<>();
        int size = currentFrequentCountList.size();
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                Integer preValue = currentFrequentCountList.get(i);
                Integer nextValue = currentFrequentCountList.get(j);
                setFrequentSetMap(preValue, nextValue, pointCount, frequentMap, itemChecklist, newCurrentFrequentCountList);
            }
        }
        return newCurrentFrequentCountList;
    }


    private void setFrequentSetMap(Integer preValue, Integer nextValue, int pointCount, Map<Integer, Integer> frequentMap, List<Integer> itemChecklist, List<Integer> newCurrentFrequentCountList) {

        int pointSet = preValue | nextValue;
        if (bitCount(pointSet) == pointCount && frequentMap.get(pointSet) == null) {
            setFrequentSetMap(pointSet, frequentMap, itemChecklist, newCurrentFrequentCountList);
        }
    }

    /**
     * //        1 dataList.add("1;2;5;");     19
     * //        2 dataList.add("2;4;");       10
     * //        3 dataList.add("2;3;");       6
     * //        4 dataList.add("1;2;4;");     11
     * //        5 dataList.add("1;3;");       5
     * //        6 dataList.add("2;3;");       6
     * //        7 dataList.add("1;3;");       5
     * //        8 dataList.add("1;2;3;5;");   23
     * //        9 dataList.add("1;2;3;");     7
     *
     * @param frequentMap
     */
    private void setFrequentSetMap(int pointSet, Map<Integer, Integer> frequentMap, List<Integer> itemChecklist, List<Integer> newCurrentFrequentCountList) {
        int count = 0;
        for (Integer itemCheck : itemChecklist) {
            if ((itemCheck & pointSet) == pointSet) {
                count++;
            }
        }
        if (count >= SUPPORT) {
            frequentMap.put(pointSet, count);
            newCurrentFrequentCountList.add(pointSet);
        }
    }

    /**
     * @param itemList
     * @param nextItemList
     * @param frequentMap
     */
    private void createAssociationRule(List<Integer> itemList, List<Integer> nextItemList, Map<Integer, Integer> frequentMap, Map<Integer, String> idItemMap) {
        if (nextItemList == null || nextItemList.isEmpty()) {
            return;
        }
        for (Integer item : itemList) {
            for (Integer nextItem : nextItemList) {
                Integer value = frequentMap.get(item);
                if ((nextItem & item) == item) {
                    Integer nextValue = frequentMap.get(nextItem);
                    float confidence = nextValue / (float) value;
                    if (value != null && nextValue != null && confidence >= CONFIDENCE) {
                        System.out.println(value + "   " + nextValue);
                        printAssociationRule(item, nextItem, confidence, idItemMap);
                    }
                }

            }
        }
    }

    /**
     * 打印关联规则
     *
     * @param item
     * @param nextItem
     * @param confidence
     * @param idItemMap
     */
    private void printAssociationRule(Integer item, Integer nextItem, float confidence, Map<Integer, String> idItemMap) {
        System.out.println(getItemStr(item, idItemMap) + " => " + getItemStr(nextItem, idItemMap) + " = " + confidence);
        System.out.println();
    }

    private String getItemStr(Integer item, Map<Integer, String> idItemMap) {
        int index = 1;
        StringBuilder sb = new StringBuilder();
        while (item != 0) {
            if ((item & 1) == 1) {
                sb.append(idItemMap.get(index));
            }
            item = item >> 1;
            index++;
        }
        return sb.toString();
    }

    /**
     * 获取一个整数 二进制 1 的个数
     *
     * @param n
     * @return
     */
    private int bitCount(int n) {
        int c;
        for (c = 0; n != 0; ++c) {
            n &= (n - 1); // 清除最低位的1
        }
        return c;
    }


    /**
     * 获取总清单的无重复货物清单
     * 构建货物ID
     *
     * @param dataList
     * @param itemSet
     * @param itemIdMap
     * @param idItemMap
     */
    private void getItemSetAndCreateItemIndex(ArrayList<String> dataList, Set<String> itemSet,
                                              List<Integer> itemChecklist, Map<String, Integer> itemIdMap, Map<Integer, String> idItemMap) {
        //对商品进行去重
        for (String itemList : dataList) {
            String[] items = itemList.split(";");
            for (String item : items) {
                itemSet.add(item);
            }
        }

        //为每件商品进行编号
        int index = 1;
        for (String item : itemSet) {
            itemIdMap.put(item, index);
            idItemMap.put(index, item);
            index++;
        }

        //获得每个清单的数字表示形式
        for (String items : dataList) {
            int length = items.length();
            int sum = 0;
            for (int i = 0; i < length; i++) {
                char ch = items.charAt(i);
                if (ch != ';') {
                    Integer id = itemIdMap.get(ch + "");
                    int pow = (int) Math.pow(2, id - 1);
                    if ((sum & pow) != pow) {
                        sum = sum + pow;
                    }
                }
            }
            itemChecklist.add(sum);
        }

    }

    /**
     * //        1 dataList.add("1;2;5;");     19
     * //        2 dataList.add("2;4;");       10
     * //        3 dataList.add("2;3;");       6
     * //        4 dataList.add("1;2;4;");     11
     * //        5 dataList.add("1;3;");       5
     * //        6 dataList.add("2;3;");       6
     * //        7 dataList.add("1;3;");       5
     * //        8 dataList.add("1;2;3;5;");   23
     * //        9 dataList.add("1;2;3;");     7
     *
     * @param frequentMap
     */
    private List<Integer> createFirstFrequentSet(Set<String> itemSet, List<Integer> itemChecklist, Map<String, Integer> itemIdMap, Map<Integer, Integer> frequentMap) {
        List<Integer> selectedItemList = new ArrayList<>();
        for (String itemStr : itemSet) {
            int count = 0;
            Integer item = itemIdMap.get(itemStr);
            int itemIndex = (int) Math.pow(2, item - 1);
            for (Integer itemCheck : itemChecklist) {
                if ((itemIndex & itemCheck) == itemIndex) {
                    count++;
                }
            }
            if (count >= SUPPORT) {
                selectedItemList.add(itemIndex);
                frequentMap.put(itemIndex, count);
            }
        }
        return selectedItemList;
    }
}
